package com.ryujung.bfs.leetCode_1162;

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    /**
     * 思路：
     * 首先找到所有的陆地，然后依次遍历陆地，
     * 遍历规则，根据当前队列的大小，遍历相同的次数，即只遍历一层，
     * 每次遍历，只移动一次，并将distance+1，然后将合法的海洋位置加入队列，然后逐层遍历
     *
     * 将陆地各自向四个方向进行移动，然后判断移动后的位置是否在边界内，并且是否为海洋
     * 如果是，就将当前的最大距离+1 ，然后将已经遍历的过的当前位置改为已遍历
     */
    public static int maxDistance(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        // 获取所有的陆地位置坐标
        Queue<int[]> que = new ArrayDeque<>();
        for (int i = 0; i < grid[0].length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    que.add(new int[]{i, j});
                }
            }
        }
        if(que.size()==grid.length* grid.length || que.size() ==0){
            return -1;
        }

        // 遍历陆地坐标
        int[][] move = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int distance = -1;

        while (!que.isEmpty()) {
            int curLevelSize = que.size();
            distance++;

            // 遍历当前层
            for (int i = 0; i < curLevelSize; i++) {
                int[] pos = que.poll();

                int x = pos[0];
                int y = pos[1];

                for (int[] eachMove : move) {
                    int x1 = x + eachMove[0];
                    int y1 = y + eachMove[1];

                    if (isInArea(grid, x1, y1) && grid[x1][y1] == 0) {
                        grid[x1][y1] = 2;
                        que.add(new int[]{x1, y1});
                    }

                }
            }
        }
        return distance;
    }

    private static boolean isInArea(int[][] grid, int x, int y) {
        return x < grid.length && y < grid[0].length && x >= 0 && y >= 0;
    }
}